#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n,m,q,f[N],las[N],lt[N],rt[N],ans[N];
int find(int x)
{
	if(f[x]==x) return x;
	return f[x] = find(f[x]);
}
vector<pair<int,int>> vec[N];
vector<int> del[N];
struct node{
	int mn,mx,res,tag;
}t[N<<2];
#define ls (k<<1)
#define rs (k<<1|1)
#define pushup(k) (t[k].mx = max(t[ls].mx,t[rs].mx),t[k].mn = min(t[ls].mn,t[rs].mn),t[k].res = min(t[ls].res,t[rs].res))
void cover(int k,int l,int r,int v)
{
	t[k].mn = t[k].mx = t[k].tag = v;
	t[k].res = l-t[k].mn;
}
void down(int k,int l,int r,int mid)
{
	if(t[k].tag!=-1)
	{
		cover(ls,l,mid,t[k].tag),cover(rs,mid+1,r,t[k].tag);
		t[k].tag = -1;
	}
}
void build(int k,int l,int r)
{
	t[k].mx = t[k].mn = t[k].res = 2e9,t[k].tag = -1;
	if(l==r) return;
	int mid = (l+r)/2;
	build(ls,l,mid),build(rs,mid+1,r);
}
void change(int k,int l,int r,int x,int v)
{
	if(l>x) return;
	if(t[k].mx<=v) return;
	if(r<=x&&t[k].mn>=v) return cover(k,l,r,v);
	int mid = (l+r)/2;
	down(k,l,r,mid);
	change(ls,l,mid,x,v),change(rs,mid+1,r,x,v);
	pushup(k);
}
int ask(int k,int l,int r,int x,int lt,int v)
{
//	cout<<"ask"<<k<<' '<<l<<' '<<r<<' '<<x<<' '<<lt<<' '<<v<<':'<<t[k].mx<<'\n';
	if(l>x||t[k].mx<lt) return 2e9;
	if(r<=x)
	{
		if(t[k].mn>=v) return l-v;
		if(t[k].mn>=lt&&t[k].mx<=v) return t[k].res;
	}
	int mid = (l+r)/2;
	down(k,l,r,mid);
	return min(ask(ls,l,mid,x,lt,v),ask(rs,mid+1,r,x,lt,v));
}
signed main()
{
	freopen("destory.in","r",stdin);
	freopen("destory.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i = 1;i<=n;i++) f[i] = i;
	for(int i = 1,u,v;i<=m;i++)
		cin>>u>>v,f[find(u)] = find(v);
	for(int i = 1;i<=n;i++)
	{
		lt[i] = las[find(i)];
		las[find(i)] = i; 
	}
	for(int i = 1;i<=n;i++) las[i] = n+1;
	for(int i = n;i;i--)
	{
		rt[i] = las[find(i)];
		las[find(i)] = i; 
	}
	for(int i = 1,l,r;i<=q;i++)
	{
		cin>>l>>r;
		vec[r].push_back({l,i}); 
	}
	build(1,1,n);
	set<int> s;
	for(int i = 1;i<=n;i++)
	{
		s.insert(i);
		for(auto j:del[i]) s.erase(j); 
		del[rt[i]].push_back(i);
		change(1,1,n,i,lt[i]);
		for(auto _:vec[i])
		{
			int l = _.first,id = _.second;
			int p = *s.lower_bound(l);
//			cout<<"xx"<<l<<' '<<i<<":"<<p<<'\n';
			ans[id] = min(ask(1,1,n,i,l,p),i-p+1);
		}
	}
	for(int i = 1;i<=q;i++) cout<<ans[i]<<'\n';
	return 0;
}

